#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include"Graph.h"
#define INF 9999999

using namespace std;

int main()
{
    //以下部分是对于Bellman-Ford算法的代码实现和测试。
    int n, m;    //存储图的顶点数和边数。
    int origin;    //存储源点下标。
    int ins = 0;    //检验是否存在自环边。
    int zero = 0;    //检验是否存在边的权重为0。
    int flag = 0;    //检验是否存在负权值回路。
    int test = 0;    //检验是否存在起终点相同的两条边。
    int max = 0;    //存储最短路径的边数限制的最大值。
    int check;    //检验是否能够继续找到最短路径。
	int dis[15], bak[15];    //两个数组均存储每个顶点对应的当前最短路径长度。
    int ans[15];    //存储每个顶点对应的最终最短路径长度。
    int u[50], v[50], w[50];    //存储边的起点、终点和权重。 

    cout << "Please enter amounts of vertexes and edges." << endl;
	cin >> n >> m;
    cout << "Please enter indexes of endpoints and weights of edges." << endl;
	for(int i = 0; i < m; i++) 
    {
		cin >> u[i] >> v[i] >> w[i];
	}
    //检验是否存在自环边。
    for(int i = 0; i < m; i++)
    {
        if(u[i] == v[i])
        {
            ins = 1;
            break;
        }
    }
    //检验是否存在边的权重为0。
    for(int i = 0; i < m; i++)
    {
        if(w[i] == 0)
        {
            zero = 1;
            break;
        }
    }
    //检验是否存在两条边起终点相同。
    for(int i = 0; i < m; i++)
    {
        for(int j = i + 1; j < m; j++)
        {
            if(u[i] == u[j] && v[i] == v[j])
            {
                test = 1;
                break;
            }
        }
    }
    if(ins == 1)    //如果有自环边，直接输出并结束操作。
    {
        cout << "There exists a self-ringed edge!" << endl;
    }
    if(test == 1)    //如果有两条边起终点相同，直接输出并结束操作。
    {
        cout << "There exist two edges with same starting points and ending points!" << endl;
    }
    if(zero == 1)
    {
        cout << "There exists an edge with the weight zero!" << endl;
    }
    if(ins == 0 && test == 0 && zero == 0)
    {
        cout << "Please enter the maximal number of edges of the shortest path." << endl;
        cin >> max;
	    //初始化dis数组，代表源点到其他顶点的初始路程。
	    for(int i = 0; i < n; i++) {
		    dis[i] = INF;
	    }
        //确认源点位置下标。
        cout << "Please enter the index of the point you want to be the origin." << endl;
        cin >> origin;
	    dis[origin] = 0; //一开始只有源点是可知的，其余的顶点都是未知。

        //Bellman-Ford算法主要过程代码
	    for(int k = 0; k < max; k++) {//最多对所有边执行max次松弛操作
		    //将dis数组备份至bak数组
		    for(int i = 0; i < n; i++) {
			    bak[i] = dis[i];
		    }
		    for(int i = 0; i < m; i++) {//对每条边执行松弛
                //若新路径的长度比已获得的路径长度小，则进行替换。
                //若当前这条边的起点已经发生了距离变动，意味着它的起点已经找到了k+1条边
                //的路径，此时不能对这条边的终点替换新路径。否则路径长度为k+2。
			    if(dis[v[i]] > dis[u[i]] + w[i] && dis[u[i]] == bak[u[i]])
				    dis[v[i]] = dis[u[i]] + w[i];
		    }
            check = 0;
		    //松弛完成后检测dis数组是否有更新。
		    for(int i = 0; i < n; i++) {
			    if(dis[i] != bak[i]) check = 1;
		    }
		    if(check == 0)  break;//如果数组不再更新就退出多余循环
	    }
        //对最终的输出数组ans进行赋值。
        for(int i = 0; i < n; i++) {
            ans[i] = dis[i];
        }

        //继续进行循环，保证总共进行n-1次循环。
	    for(int k = max; k < n - 1; k++) {
		    //将dis数组备份至bak数组
		    for(int i = 0; i < n; i++) {
			    bak[i] = dis[i];
		    }
		    for(int i = 0; i < m; i++) {//对每条边执行松弛
			    if(dis[v[i]] > dis[u[i]] + w[i])
				    dis[v[i]] = dis[u[i]] + w[i];
		    }
            check = 0;
		    //松弛完成后检测dis数组是否有更新
		    for(int i = 0; i < n; i++) {
			    if(dis[i] != bak[i]) check = 1;
		    }
		    if(check == 0)  break;//如果数组不再更新就退出多余循环
	    }
	    //检测是否有负权值回路。
	    for(int i = 0; i < m; i++) {
		    if(dis[v[i]] > dis[u[i]] + w[i]) flag = 1; //如果还能继续松弛，则代表有负权值回路。
	    }
	    if(flag == 1)    //如果有负权值回路，则直接输出。
		    cout << "There exists a negative weighted loop!" << endl;
        else{
            //没有异常情况，输出每个顶点相对于源点的最短路径长度。
	        for(int i = 0; i < n; i++) {
		        cout << ans[i] << " ";
	        }
            cout << endl;
        }
    }   

    cout << "Now we finish the operation for path lookup." << endl;
    cout << endl;

    //以下是对于基本操作的效率测试。
    Graph1<int, int> graph11(200);
    Graph1<int, int> graph21(400);
    Graph1<int, int> graph31(600);
    Graph1<int, int> graph41(800);
    Graph1<int, int> graph51(1000);
    Graph2<int, int> graph12(200);
    Graph2<int, int> graph22(400);
    Graph2<int, int> graph32(600);
    Graph2<int, int> graph42(800);
    Graph2<int, int> graph52(1000);
    int a1,a2,a3,a4,a5;
    int b1,b2,b3,b4,b5;
    double time11 = 0,time21 = 0,time31 = 0,time41 = 0,time51 = 0;
    double time12 = 0,time22 = 0,time32 = 0,time42 = 0,time52 = 0;

    //测试函数addEdge。
/*    for(int i=0;i<200;i++){
        graph11.addPoint(i);
        graph12.addVertex(i);
    }
    for(int i=0;i<400;i++){
        graph21.addPoint(i);
        graph22.addVertex(i);
    }
    for(int i=0;i<600;i++){
        graph31.addPoint(i);
        graph32.addVertex(i);
    }
    for(int i=0;i<800;i++){
        graph41.addPoint(i);
        graph42.addVertex(i);
    }
    for(int i=0;i<1000;i++){
        graph51.addPoint(i);
        graph52.addVertex(i);
    }   

    for(int i=0;i<5000;i++){
        srand(unsigned(time(0)));
        a1 = rand() % 200;
        srand(unsigned(time(0)));
        b1 = rand() % 200;
        clock_t begintime11 = clock();
        graph11.addEdge(a1,b1,1);
        clock_t endtime11 = clock();
        clock_t begintime12 = clock();
        graph12.addEdge(a1,b1,1);  
        clock_t endtime12 = clock();
        time11 += double(endtime11 - begintime11) / CLOCKS_PER_SEC;
        time12 += double(endtime12 - begintime12) / CLOCKS_PER_SEC;
    }
    time11 /= 5000;
    time12 /= 5000;
    for(int i=0;i<5000;i++){
        srand(unsigned(time(0)));
        a2 = rand() % 400;
        srand(unsigned(time(0)));
        b2 = rand() % 400;
        clock_t begintime21 = clock();
        graph21.addEdge(a2,b2,1);
        clock_t endtime21 = clock();
        clock_t begintime22 = clock();
        graph22.addEdge(a2,b2,1);
        clock_t endtime22 = clock();
        time21 += double(endtime21 - begintime21) / CLOCKS_PER_SEC;
        time22 += double(endtime22 - begintime22) / CLOCKS_PER_SEC;
    }
    time21 /= 5000;
    time22 /= 5000;
    for(int i=0;i<5000;i++){
        srand(unsigned(time(0)));
        a3 = rand() % 600;
        srand(unsigned(time(0)));
        b3 = rand() % 600;
        clock_t begintime31 = clock();
        graph31.addEdge(a3,b3,1);
        clock_t endtime31 = clock();
        clock_t begintime32 = clock();
        graph32.addEdge(a3,b3,1);
        clock_t endtime32 = clock();
        time31 += double(endtime31 - begintime31) / CLOCKS_PER_SEC;
        time32 += double(endtime32 - begintime32) / CLOCKS_PER_SEC;
    }
    time31 /= 5000;
    time32 /= 5000;
    for(int i=0;i<5000;i++){
        srand(unsigned(time(0)));
        a4 = rand() % 800;
        srand(unsigned(time(0)));
        b4 = rand() % 800;
        clock_t begintime41 = clock();
        graph41.addEdge(a4,b4,1);
        clock_t endtime41 = clock();
        clock_t begintime42 = clock();
        graph42.addEdge(a4,b4,1);
        clock_t endtime42 = clock();
        time41 += double(endtime41 - begintime41) / CLOCKS_PER_SEC;
        time42 += double(endtime42 - begintime42) / CLOCKS_PER_SEC;
    }
    time41 /= 5000;
    time42 /= 5000;
    for(int i=0;i<5000;i++){
        srand(unsigned(time(0)));
        a5 = rand() % 1000;
        srand(unsigned(time(0)));
        b5 = rand() % 1000;
        clock_t begintime51 = clock();
        graph51.addEdge(a5,b5,1);
        clock_t endtime51 = clock();
        clock_t begintime52 = clock();
        graph52.addEdge(a5,b5,1);
        clock_t endtime52 = clock();
        time51 += double(endtime51 - begintime51) / CLOCKS_PER_SEC;
        time52 += double(endtime52 - begintime52) / CLOCKS_PER_SEC;
    }    
    time51 /= 5000;
    time52 /= 5000;   */

    //测试函数removePoint和removeVertex。
    //对于每个顶点数构建完全图。
    for(int i = 0; i < 200; i++){
        for(int j = 0; j < 200; j++){
            if(i == j) break;
            else{
                graph11.addEdge(i,j,1);
                graph12.addEdge(i,j,1);
            }
        }
    }
    for(int i = 0; i < 400; i++){
        for(int j = 0; j < 400; j++){
            if(i == j) break;
            else{
                graph21.addEdge(i,j,1);
                graph22.addEdge(i,j,1);
            }
        }
    }
    for(int i = 0; i < 600; i++){
        for(int j = 0; j < 600; j++){
            if(i == j) break;
            else{
                graph31.addEdge(i,j,1);
                graph32.addEdge(i,j,1);
            }
        }
    }
    for(int i = 0; i < 800; i++){
        for(int j = 0; j < 800; j++){
            if(i == j) break;
            else{
                graph41.addEdge(i,j,1);
                graph42.addEdge(i,j,1);
            }
        }
    }
    for(int i = 0; i < 1000; i++){
        for(int j = 0; j < 1000; j++){
            if(i == j) break;
            else{
                graph51.addEdge(i,j,1);
                graph52.addEdge(i,j,1);
            }
        }
    }

    srand(unsigned(time(0)));
    a1 = rand() % 200;
    clock_t begintime11 = clock();
    graph11.removePoint(a1);
    clock_t endtime11 = clock();
    clock_t begintime12 = clock();
    graph12.removeVertex(a1);  
    clock_t endtime12 = clock();
    time11 += double(endtime11 - begintime11) / CLOCKS_PER_SEC;
    time12 += double(endtime12 - begintime12) / CLOCKS_PER_SEC;

    srand(unsigned(time(0)));
    a2 = rand() % 400;
    clock_t begintime21 = clock();
    graph21.removePoint(a2);
    clock_t endtime21 = clock();
    clock_t begintime22 = clock();
    graph22.removeVertex(a2);  
    clock_t endtime22 = clock();
    time21 += double(endtime21 - begintime21) / CLOCKS_PER_SEC;
    time22 += double(endtime22 - begintime22) / CLOCKS_PER_SEC;

    srand(unsigned(time(0)));
    a3 = rand() % 600;
    clock_t begintime31 = clock();
    graph31.removePoint(a3);
    clock_t endtime31 = clock();
    clock_t begintime32 = clock();
    graph32.removeVertex(a3);  
    clock_t endtime32 = clock();
    time31 += double(endtime31 - begintime31) / CLOCKS_PER_SEC;
    time32 += double(endtime32 - begintime32) / CLOCKS_PER_SEC;

    srand(unsigned(time(0)));
    a4 = rand() % 800;
    clock_t begintime41 = clock();
    graph41.removePoint(a4);
    clock_t endtime41 = clock();
    clock_t begintime42 = clock();
    graph42.removeVertex(a4);  
    clock_t endtime42 = clock();
    time41 += double(endtime41 - begintime41) / CLOCKS_PER_SEC;
    time42 += double(endtime42 - begintime42) / CLOCKS_PER_SEC;

    srand(unsigned(time(0)));
    a5 = rand() % 1000;
    clock_t begintime51 = clock();
    graph51.removePoint(a5);
    clock_t endtime51 = clock();
    clock_t begintime52 = clock();
    graph52.removeVertex(a5);  
    clock_t endtime52 = clock();
    time51 += double(endtime51 - begintime51) / CLOCKS_PER_SEC;
    time52 += double(endtime52 - begintime52) / CLOCKS_PER_SEC;

    cout << time11 << endl;
    cout << time12 << endl;
    cout << time21 << endl;
    cout << time22 << endl;
    cout << time31 << endl;
    cout << time32 << endl;
    cout << time41 << endl;
    cout << time42 << endl;
    cout << time51 << endl;
    cout << time52 << endl;   



	return 0;
}